package com.modular.Shortest_path;

import java.util.*;


//图的算法一般都采用邻接表来存储，避免了过于系数
public class template {
    //地杰斯特拉的堆优化  处理有向图
    /*从一个顶点到其余各顶点的最短路径算法，解决的是有权图中最短路径问题。
    迪杰斯特拉算法主要特点是从起始点开始，采用贪心算法的策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。
    Dijkstra
        本质是贪心+广搜
        朴素写法，时间复杂度O(V^2+E)O(V2+E)，可以认为是O(V^2)O(V2)，
        这个一般不怎么写，需要松弛，太蠢啦
        堆优化（小堆），时间复杂度O(VlogV+E)O(VlogV+E)
        DijkstraDijkstra 算法更适合稠密图（边多的图）
        无论图有没有环，DijkstraDijkstra 算法都是可以用的，它只是不能处理负权边，因为它本质上是贪心策略，每个点选择之后就不再更新，如果碰到了负边的存在就会破坏这个贪心的策略就无法处理了
        一般堆优化+邻接表 用起来贼爽
*/

    public int dijkStra1(int n,int [][]edges,int start,int end){
        //这里的edges = [[begin,end,times],...]这种形式的，也可能是其他形式的，处理方式类似
        Map<Integer, ArrayList<int[]>> graph = new HashMap<>();
        for(int []edge:edges){
            int begin = edge[0];
            int endindex = edge[1];
            int time = edge[2];//这条边的权重
            if(!graph.containsKey(begin))//先判断是否存在begin的集合
                graph.put(begin,new ArrayList<int []>());
            graph.get(begin).add(new int[]{endindex,time});
        }

        //dist数组和visit数组 一个存到当前点的最短路径，一个判断是否访问过
        int []dist = new int[n];//如果从1开始也可以 长度初始化为n+1
        boolean []visit = new  boolean[n];

        //初始化disit数组，根据题目意思初始化 ，如果求最短，则将其初始化为最大；反之一样。
        Arrays.fill(dist,Integer.MAX_VALUE);//默认求最短路径
        dist[start] = 0;//起点一定要记得初始化为0 ！！！

        //new一个小堆出来，按照dis升序排，一定要让它从小到大排，省去了松弛工作
        Queue<Integer> queue = new PriorityQueue<>((o1, o2) -> dist[o1]-dist[o2]);
        //起点入队
        queue.offer(start);
        while (!queue.isEmpty()){
            //获取队头
            int nowindex = queue.poll();//当前队头

            if(visit[nowindex]) continue;
            visit[nowindex] = true;
            //
            ArrayList<int[]> ints = graph.get(nowindex);
            if(ints == null) continue;
            for (int[] anInt : ints) {
                int next = anInt[0];

                if(visit[next]) continue;//已经访问过了
                //这里也有可能是求最长路径，或者是别的变形，就是换一下形式；
                dist[next] =  Math.min(dist[next], dist[nowindex] + anInt[1]);
                queue.offer(next);
            }
        }
        //返回start->end的最短路径， 如果结果为MAX_VALUE，说明无最短，根据题目要求返回要求值
        return dist[end]==Integer.MAX_VALUE?-1:dist[end];
    }

    //地杰斯特拉处理无向图
    public int dijkStra2(int n,int [][]edges,int start,int end){
        Map<Integer, Map<Integer, Integer>> map = new HashMap<>();
        for (int[] edge : edges) {
            int begin = edge[0], endindex = edge[1], time = edge[2];
            //将a->b存入集合
            Map<Integer, Integer> am = map.getOrDefault(begin, new HashMap<Integer, Integer>());
            am.put(endindex, time);
            map.put(begin, am);

            //将b->a存入集合
            Map<Integer, Integer> bm = map.getOrDefault(endindex, new HashMap<Integer, Integer>());
            bm.put(begin, time);
            map.put(endindex, bm);
        }

        // 堆优化 Dijkstra：求 每个点 到 第n个点 的最短路
        int[] dist = new int[n];
        boolean[] st = new boolean[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;//
        //Queue<int[]> queue = new PriorityQueue<int[]>((a, b) -> a[1] - b[1]); // 点编号，点距离。根据点距离从小到大
        PriorityQueue<Integer> queue = new PriorityQueue<>((o1,o2)->dist[o1]-dist[02]);
        queue.offer(start);
        //queue.offer(new int[]{start, 0});
        while (!queue.isEmpty()) {
            //int[] e = queue.poll();//获取队头
            int idx = queue.poll();
           // int idx = e[0], cur = e[1];
            if (st[idx]) continue;
            st[idx] = true;
            Map<Integer, Integer> mm = map.get(idx);
            if (mm == null) continue;
            for (int i : mm.keySet()) {
                dist[i] = Math.min(dist[i], dist[idx] + mm.get(i));
               // queue.add(new int[]{i, dist[i]});
                queue.add(i);
            }
        }
        //返回start->end的最短路径， 如果结果为MAX_VALUE，说明无最短，根据题目要求返回要求值
        return dist[end]==Integer.MAX_VALUE?-1:dist[end];
    }

    //bellman
    /*
    * 有时候这种算法也被称为 Moore-Bellman-Ford 算法，
    * 因为 Edward F. Moore 也为这个算法的发展做出了贡献。
    * 它的原理是对图进行V-1次松弛操作，得到所有可能的最短路径。
    * 其优于迪科斯彻算法的方面是边的权值可以为负数、实现简单，
    * 缺点是时间复杂度过高，高达O(VE)。但算法可以进行若干种优化，提高了效率。
    * */
    public int Bellman_Ford(int[][] times, int n, int K) {
        // 存放 K 到各个点的最短路径，最大的那个最短路径即为结果
        int[] distance = new int[ n+ 1];
        Arrays.fill(distance, Integer.MAX_VALUE);
        distance[K] = 0;//K可以是起点

        // 进行 n-1 轮的松弛，因为任意两点间的最短路径最多包含 n-1 条边
        for (int i = 1; i <= n - 1; i++) {
            for (int[] time : times) {
                // 源节点
                int u = time[0];
                // 目标节点
                int v = time[1];
                // 一个信号源从源节点到目标节点的时间
                int w = time[2];
                // 判断能否通过 u->v 缩短 distance[v]（松弛）
                if (distance[u] != Integer.MAX_VALUE) {
                    //必定要更新
                    if (distance[v] == Integer.MAX_VALUE) {
                        distance[v] = distance[u] + w;
                    } else {
                        //判断值的大小
                        distance[v] = Math.min(distance[v], distance[u] + w);
                    }
                }
            }
        }
        return distance[n];
    }

    //spfa算法是对bellman的优化 处理有向图
    /*
    * 它是 Bellman-FordBellman−Ford 的优化， Bellman-Ford Bellman−Ford 的时间复杂度为 O(VE)O(VE)，
    * 效率太低了，SPFASPFA 是 Bellman-FordBellman−Ford 的队列优化，但是算法时间效率不稳定，时间复杂度为 O(E)O(E)，
    * 最好情况下，每个节点只入队一次，就是 BFSBFS，最坏情况下，每一个节点都要入队 V-1V−1 次，这时候就退化成 Bellman-FordBellman−Ford 了
      SPFA 时间复杂度某种情况下略高于 DijkstraDijkstra， 适合稀疏图
      SPFA 是可以用于带有负权图的，在 SPFASPFA 中每一个点松弛过后说明这个点距离更近了，所以有可能通过这个点会再次优化其他点，
      * 所以它的策略是将 visvis 位置为 falsefalse，把这个点入队再判断一次！这就和 DijkstraDijkstra 的贪心策略不同了！
      SPFA 还有个用处是可以判断图是否存在负环，我们只要用一个 cnt[x]cnt[x] 数组来存放经过这个点的次数，
      * 上面提到过，最坏情况下每个节点入队 V-1V−1 次，如果 cnt[x]cnt[x] 为 VV 的个数，那就说明存在负环了。
    西南交通大学的段凡丁于1994年提出了用队列来优化的算法。松弛操作必定只会发生在最短路径前导节点松弛成功过的节点上，
    用一个队列记录松弛过的节点，可以避免了冗余计算。
    * */
    public int spfa(int n, int[][] edges, int start, int end){
        //这里的edges = [[begin,end,times],...]这种形式的，也可能是其他形式的，处理方式类似
        Map<Integer, ArrayList<int[]>> graph = new HashMap<>();
        for(int []edge:edges){
            int begin = edge[0];
            int endindex = edge[1];
            int time = edge[2];//这条边的权重
            if(!graph.containsKey(begin))//先判断是否存在begin的集合
                graph.put(begin,new ArrayList<int []>());
            graph.get(begin).add(new int[]{endindex,time});
        }

        // 初始化dis数组和vis数组
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        boolean[] visit = new boolean[n];
        dist[start] = 0;

        Queue<Integer> queue = new LinkedList<>();
        queue.offer(start);

        while (!queue.isEmpty()) {
            // 取出队首节点
            Integer poll = queue.poll();
            // 可以重复入队
            visit[poll] = false;
            // 遍历起点的邻居,更新距离
            ArrayList<int[]> list = graph.get(poll);
            if(list == null) continue;//为空直接跳过

            for (int[] arr : list) {
                int next = arr[0];
                // 如果没更新过，或者需要更新距离()
                if (dist[next] == Integer.MAX_VALUE || dist[next] > dist[poll] + arr[1]) {
                    // 更新距离
                    dist[next] = dist[poll] + arr[1];
                    // 如果队列中没有，就不需要再次入队了 （那么判断入度可以在这里做文章）
                    if (!visit[next]) {
                        visit[next] = true;
                        queue.offer(next);
                    }
                }
            }
        }
        //int res = Arrays.stream(dist).max().getAsInt();

        return dist[end] == Integer.MAX_VALUE ? -1 : dist[end];
    }

    //处理无向图 可以借助一个List<List<Integer>>来存储
    //https://leetcode-cn.com/problems/number-of-restricted-paths-from-first-to-last-node/solution/spfa-tuo-bu-pai-xu-by-zhifeichong-gqci/


    //Floyd算法

    public static int Floyd(int[][] times, int n, int K) {
        int[][] g = new int[n + 1][n  + 1];
        // 初始化图,注意,一开始距离是初始化为INF的，而不是像 spfa初始化成-1
        // spfa初始化成-1只是为了判断是否为邻居，这里初始化为INF是因为要取min的
        for (int i = 1; i <= n ; i++) {
            for (int j = 1; j <= n ; j++) {
                g[i][j] = i == j ? 0 : Integer.MAX_VALUE;
            }
        }
        for (int[] t : times) {
            g[t[0]][t[1]] = t[2];
        }
        // 使用K节点来松弛i->j的最短路径（大白话就是利用k作为中间节点）
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    // 判断语句可以不用写，具体得看题目
                     if (k != i && k != j && g[i][k] != Integer.MAX_VALUE && g[k][j] != Integer.MAX_VALUE) {
                    g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
                    }
                }
            }
        }
        // g[a][b]表示a到b的最短距离
        // 拿结果
        int res = 0;
        for (int distance : g[K]) {
            res = Math.max(res, distance);
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

}
